var serialize = function(root) {
  // 为了保证顺序使用广度优先遍历算法，将不对称的子树用null补充，将数中的值存储为list
  const serializeQueue = []
  const traverse = function(queue){
      const newQueue = []
      queue.forEach((item)=>{
          if(item){
              serializeQueue.push(item.val)
              newQueue.push(item.left)
              newQueue.push(item.right)
          }else{
              serializeQueue.push(null)
          }
      })
      if(newQueue.length>0){
          traverse(newQueue)
      }
  }
  if(root){
      traverse([root])
  }
  return JSON.stringify(serializeQueue)
};

/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function(data) {
  const serializeQueue = JSON.parse(data)
  // 给一层添加子元素
  // 删除已使用的子元素
  // 如果队列为空，说明无子元素可以使用，退出
  if(serializeQueue.length===0){
      return null
  }
  const rootVal = serializeQueue.shift()
  const root = new TreeNode(rootVal)
  const traverse = function(queue){
      const newQueue = [] // 保存下一层待添加子节点的节点
      queue.forEach((node)=>{
          // 取左节点
          const left =  serializeQueue.shift()
          if(left!==null){
              const leftNode = new TreeNode(left)
              newQueue.push(leftNode)
              node.left = leftNode
          }else{
              node.left = null
          }
          // 取右节点
          const right =  serializeQueue.shift()
          if(right!==null){
              const rightNode = new TreeNode(right)
              newQueue.push(rightNode)
              node.right = rightNode
          }else{
              node.right = null
          }

      })
      if(serializeQueue.length){
          traverse(newQueue)
      }
  }
  traverse([root])
  return root
};
